/**
 * 二分
 * @param array 数组
 * @param num 查找的数字
 * @returns 返回索引
 * 1个或者0个用其他判断方式，长度直接除2，两边进行判断，找到再范围内的一端，开始递归
 */
export function binarySearch(array: number[], num: number): number {
  if (array.length === 0) return -1;
  if (array.length === 1) return array[0] === num ? 0 : -1;

  const middle = Math.floor(array.length / 2);

  if (array[middle] === num) {
    return middle;
  } else {
    let arr = [];
    let lIdx = 0;
    if (array[middle] > num) {
      arr = array.slice(0, middle);
    } else {
      arr = array.slice(middle);
      lIdx += middle;
    }
    if (arr.length === 0) return -1;
    const res = binarySearch(arr, num);
    if (res !== -1) return lIdx + res;
  }

  return -1;
}

// const index = binarySearch([1, 2, 3, 4, 6, 7, 8, 9], 6);
// console.log("---", index);

// 非递归，左右下标切换达到效果，老师的方式 二分查找
export function binarySearch2(array: number[], num: number): number {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    // console.log("left", left, "right", right);

    let mid = Math.floor((left + right) / 2);
    if (array[mid] === num) {
      return mid;
    } else if (array[mid] > num) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

// const index2 = binarySearch2([1, 2, 3, 4, 6, 7, 8, 9], 2);
// console.log("-index-", index2);
export {};
